package LeetCode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class LC_378_KthSmallestElementinaSortedMatrix {

    public static void main(String[] args) {

    }

    public class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            int n = matrix.length;
            int L = matrix[0][0], R = matrix[n - 1][n - 1];
            while (L < R) {
                int mid = L + ((R - L) >> 1);
                int temp = 0;
                for (int[] aMatrix : matrix) temp += binary_search(aMatrix, n, mid);
                if (temp < k) L = mid + 1;
                else R = mid;
            }
            return L;
        }

        private int binary_search(int[] row, int R, int x) {
            int L = 0;
            while (L < R) {
                int mid = (L + R) >> 1;
                if (row[mid] <= x) L = mid + 1;
                else R = mid;
            }
            return L;
        }
    }

    //优先队列
    class Pair {
        int x, y, val;

        Pair(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }

    class PairComparator implements Comparator<Pair> {
        public int compare(Pair a, Pair b) {
            return a.val - b.val;
        }
    }

    public class Solution_2 {
        public int kthSmallest(int[][] matrix, int k) {
            int[] dx = new int[]{0, 1};
            int[] dy = new int[]{1, 0};
            int n = matrix.length;
            int m = matrix[0].length;
            boolean[][] hash = new boolean[n][m];
            PriorityQueue<Pair> minHeap = new PriorityQueue<>(k, new PairComparator());
            minHeap.add(new Pair(0, 0, matrix[0][0]));
            for (int i = 0; i < k - 1; i++) {
                Pair cur = minHeap.poll();
                for (int j = 0; j < 2; j++) {
                    int next_x = cur.x + dx[j];
                    int next_y = cur.y + dy[j];
                    Pair next_Pair = new Pair(next_x, next_y, 0);
                    if (next_x < n && next_y < m && !hash[next_x][next_y]) {
                        hash[next_x][next_y] = true;
                        next_Pair.val = matrix[next_x][next_y];
                        minHeap.add(next_Pair);
                    }
                }
            }
            return minHeap.peek().val;
        }
    }

}